
public class JumpGameII {
	public void tester() {
		int [] a= {3,1,1,1,1};
		System.out.println(jump(a));
	}
	
    public int jump(int[] A) {
        if(A.length < 2) return 0;
        
        int [] cost = new int [A.length];
        int a = 1;
        
        for(int i = 0; i < A.length-1 ; i++) {
            markRange(a, i + A[i], cost, cost[i]+1);
            
            if(A[i]+i+1 > a)
            	a = A[i]+i+1;
            
            if(cost[cost.length-1] != 0) return cost[cost.length-1];
        }
        
        return cost[cost.length-1];
    }
    
    public void markRange(int a, int b, int [] cost, int c) {
        for(int i = a ; i <= b && i < cost.length ; i++) {
            cost[i] = c;
            
        }
    }
}